There is a general algorithm for filling polygons as described in J. D. Foley and A. Van Dam, Fundamentals of Interactive Computer Graphics (Addison-Wesley, 1982), pages 456-460. This general algorithm is referred to as an edge table driven algorithm. This type of algorithm is used in computer graphic applications as one of the standard routines that are called to perform certain graphic tasks. Some of these graphic tasks include drawing lines, circles, arcs, etc., including filling polygons. These tasks are typically supplied in a library containing graphical functions such as a Graphics Support Library (GSL). In general, a graphics support library is a package of graphic subroutines that are typically delivered with a processing system so that users can write to displays with a higher level interface without having to know the complexity of any particular display and how to write to that display.
For some simpler shapes of polygons, this algorithm becomes too time consuming. An algorithm becomes unduly time consuming when users of graphical applications have to wait after they have selected the polygon fill routine from a graphics library before the display screen displays the resulting filled polygon. It is important for customer satisfaction that the fill rate be as fast as possible without trading off the accuracy of the filled polygon.
In another known algorithm, the algorithm routine uses the Bresenham algorithm defined in J. E. Bresenham, "Algorithm for Computer Control of a Digital Plotter", IBM Systems Journal, Vol. 4, No. 1 (1965), pages 25-30. The Bresenham algorithm is also described in J. D. Foley and A. Van Dam, Fundamentals of Interactive Computer Graphics (Addison-Wesley), 1982), pages 433-436. The Bresenham algorithm is used to scan the lines of the polygon boundary, and to generate the points that make up the polygon boundary. However, this known polygon fill algorithm selects the first point after a change in the scan line. The problem with this algorithm is that it does not accurately fill within the boundaries of the polygon. The resulting displayed polygon will appear as if it is incompletely filled. That is, the fill does not reach the boundary of the polygon at all locations.
There are a variety of different shapes of polygons. Depending on the shape of a particular polygon, there may exist a polygon fill routine that is more efficient for that particular polygon shape than for other polygons having a different shape. The article "Method To Determine The Convexity of Polygons", IBM Technical Disclosure Bulletin Vol. 28 No. 5 October 1985 pages 2203 to 2208 discloses that for convex polygons, there exist filling algorithms which are more efficient than those for general polygons.
By referring to FIG. 1A, the above mentioned article states that a polygon 10 is convex if all of its interior angles at the vertices A, B, C, D, E, are less than 1/2degrees. FIG. 1B illustrates a polygon 11 that is not convex by this definition since it has an interior angle at its vertex E which is greater than 180 degrees.
A method is disclosed in the article that determines whether or not all interior angles are less than 180 degrees, and therefore whether or not the polygon is convex. The method takes the cross product for each two adjoining vectors given by the edges of the polygon. If all of the cross products have the same sign, then the polygon is convex. The cross product indicates whether each side of the polygon is turning in the same direction. As shown in FIG. 1A, proceeding around the polygon 10 in the direction shown by the arrow 12 and starting at vertex E, all turns are to the left. However, in FIG. 1B, proceeding around the polygon 11 in the directions shown by the arrow 13 and starting at vertex D, all turns are to the left, except the turn at vertex E which is to the right.
The above test would thereby classify the polygons 20, 21 shown in FIG. 2A and 2B as being convex since all interior angles are less than 180 degrees. Also, as shown in either FIG. 2A or FIG. 2B, in proceeding around the polygon 20, 21 in the direction shown by the arrow 22, 23 and starting at vertex B, all turns are to the left. However, the polygons 20, 21 shown in FIG. 2A and 2B have crossing lines and turn more than once around. These type of polygons are more complex and are not accurately filled by the simpler and more efficient fill algorithms previously known in the art. Therefore, the method described in the above mentioned article does not correctly determine the convexity of polygons for all types of polygons.
Another problem is that the previous methods of testing polygons classified polygons having shapes as shown in FIG. 3A and 3B together with all other general polygons. The polygons 30, 31 of FIG. 3A and FIG. 3B are known as having x-concavity. Also, the polygon 31 of FIG. 3B has both x-concavity and crossing lines.